【忍者算法】Google搜索框背后的算法：带你深入理解前缀树｜LeetCode 208 实现Trie（前缀树）

你有没有好奇过，当你在搜索框输入时，为什么能瞬间给出相关的搜索建议？今天，让我们揭开这个神奇功能背后的数据结构：Trie（前缀树）。

🌟 生活中的前缀树

想象你在整理一本英语词典：

• 所有以'a'开头的词放在A章节
• 在A章节中，再按第二个字母分类
• 以此类推...

这种层层递进的组织方式，就是前缀树的思想！

💡 前缀树是什么？

Trie（读作"try"或"tree"）是一种树形数据结构：

• 每个节点代表一个字符
• 从根节点到某个节点的路径表示一个字符串
• 特别适合用来存储和查找字符串集合

🎨 可视化理解

假设我们要存储这些单词：

       root
         |
         c
         |
         a
       /   \
      t     r
            |
            d

看到了吗？这就像一个字符串的"家谱树"！

⚡ 完整代码实现

class Trie {
    private class TrieNode {
        private TrieNode[] children;  // 子节点数组
        private boolean isEnd;        // 标记是否是单词结尾
        
        public TrieNode() {
            children = new TrieNode[26];  // 26个小写字母
            isEnd = false;
        }
    }
    
    private TrieNode root;  // 根节点
    
    public Trie() {
        root = new TrieNode();
    }
    
    // 插入单词
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';  // 获取字符对应的索引
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEnd = true;  // 标记单词结尾
    }
    
    // 查找单词
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd;  // 必须完整匹配且是单词结尾
    }
    
    // 查找前缀
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;  // 只需要前缀匹配
    }
    
    // 查找公共方法
    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return null;  // 中途找不到，直接返回null
            }
            node = node.children[index];
        }
        return node;
    }
}

🎬 模拟运行过程

让我们一步步看看如何构建一个前缀树：

1. 初始状态：
   root

2. 插入"cat"：
   root
    |
    c
    |
    a
    |
    t*   (* 表示单词结尾)

3. 插入"car"：
   root
    |
    c
    |
    a
   / \
  t*  r*

4. 再插入"card"：
   root
    |
    c
    |
    a
   / \
  t*  r*
      |
      d*

🔍 核心操作解析

1. 插入操作

就像在建立一个文件目录：

• 沿着已有的路径走
• 如果没路了，就新建路径
• 最后标记一下这是个完整的词

2. 查找操作

像是在玩寻宝游戏：

• 顺着路径一直走
• 中途断了就返回false
• 找到了还要检查是否是完整的词

3. 前缀查找

和普通查找类似，但更宽松：

• 不需要走到尽头
• 只要能找到这段路径就行

📊 复杂度分析

时间复杂度：

• 插入：O(m)，m是单词长度
• 查找：O(m)
• 前缀查找：O(m)

空间复杂度：

• O(TOTAL)，TOTAL是所有单词字符数的总和

🎯 实战应用场景

1. 搜索引擎的自动补全
2. 拼写检查器
3. IP地址路由表
4. 文件系统的路径管理

💡 性能优化技巧

1. 压缩前缀树：合并单一路径的节点

优化前：      优化后：
  c            ca
  |     →      |
  a            t
  |
  t

2. 使用HashMap代替数组：

private Map<Character, TrieNode> children;  // 更灵活，支持更多字符

🎁 思考题

如何修改代码实现以下功能：

1. 统计某个前缀出现的次数？
2. 支持删除操作？
3. 查找最长公共前缀？

如果你知道答案，或者有自己的想法？欢迎在评论区留言、讨论～

📝 代码模板总结

实现Trie时的核心要点：

1. 定义节点结构（children数组 + 结束标记）
2. 实现三个基本操作（插入、查找、前缀查找）
3. 抽取公共查找逻辑
4. 注意字符索引转换

---

作者：忍者算法
公众号：忍者算法

🎯 回复【刷题清单】获取更多经典题目解析 👥 回复【加群】加入算法/面试交流群，一起学习进步 🧑‍💻 回复【代码】获取GitHub完整题解项目，包含Java/Python/JavaScript/Go/C++多语言实现

#算法面试 #LeetCode #数据结构 #前缀树